TNotes.leetcode

Appearance

0136. 只出现一次的数字【简单】

0136. 只出现一次的数字【简单】 ​

1. 📝 题目描述 ​

给你一个 非空 整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

  • 输入：nums = [2,2,1]
  • 输出：1

示例 2 ：

  • 输入：nums = [4,1,2,1,2]
  • 输出：4

示例 3 ：

  • 输入：nums = [1]
  • 输出：1

提示：

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • 除了某个元素只出现一次以外，其余每个元素均出现两次。

2. 🎯 s.1 - 异或运算 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let result = 0

  // 对数组中所有元素进行异或运算
  for (let i = 0; i < nums.length; i++) {
    result ^= nums[i]
  }

  return result
}
  • 时间复杂度：O(n) - 需要遍历数组一次，对每个元素执行常数时间的异或操作
  • 空间复杂度：O(1) - 只使用了一个额外变量 result，空间占用为常数级别

3. 🎯 s.2 - 使用 Map 计数 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  // 使用 Map 统计每个数字出现的次数
  const map = new Map()

  // 遍历数组，统计每个数字出现的次数
  for (const num of nums) {
    map.set(num, (map.get(num) || 0) + 1)
  }

  // 找到出现次数为 1 的数字
  for (const [num, count] of map) {
    if (count === 1) {
      return num
    }
  }
}
  • 时间复杂度：O(n) - 需要遍历数组两次，第一次统计频次，第二次查找出现次数为 1 的元素，均为线性时间
  • 空间复杂度：O(n) - 使用了 Map 数据结构存储每个元素及其出现次数，最坏情况下需要存储 n 个不同的元素

4. 🎯 s.3 - 使用 Set ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  const set = new Set()

  // 遍历数组，如果数字已在集合中则删除，否则添加
  for (const num of nums) {
    if (set.has(num)) {
      set.delete(num)
    } else {
      set.add(num)
    }
  }

  // 集合中剩下的唯一元素就是只出现一次的数字
  return [...set][0]
}
  • 时间复杂度：O(n) - 需要遍历数组一次，每次对 Set 的操作（添加、删除、检查）都是常数时间
  • 空间复杂度：O(n) - 使用了 Set 数据结构，在最坏情况下需要存储一半的元素（当遍历到一半时）

5. 🎯 s.4 - 数学求和 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  // 使用 Set 获取所有不重复的数字
  const set = new Set(nums)

  // 计算所有不重复数字的和的两倍
  let sumOfUnique = 0
  for (const num of set) {
    sumOfUnique += num
  }
  sumOfUnique *= 2

  // 计算数组中所有数字的和
  let sumOfAll = 0
  for (const num of nums) {
    sumOfAll += num
  }

  // 两者之差就是只出现一次的数字
  return sumOfUnique - sumOfAll
}
  • 时间复杂度：O(n) - 需要遍历数组一次构建 Set，遍历 Set 一次计算唯一元素和，再遍历数组一次计算总和，均为线性时间
  • 空间复杂度：O(n) - 使用了 Set 数据结构存储所有不重复的元素

6. 🎯 s.5 - 排序 ➕ 双指针查找 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  // 先对数组进行排序
  nums.sort((a, b) => a - b)

  // 使用双指针，以步长为2的方式遍历
  for (let i = 0; i < nums.length - 1; i += 2) {
    // 如果当前元素不等于下一个元素，说明当前元素是只出现一次的数字
    if (nums[i] !== nums[i + 1]) {
      return nums[i]
    }
  }

  // 如果前面都没找到，说明最后一个元素是只出现一次的数字
  return nums[nums.length - 1]
}
  • 时间复杂度：O(nlog⁡n) - 主要时间消耗在排序操作上，排序时间复杂度为 O(nlog⁡n)，后续的遍历为 O(n)
  • 空间复杂度：O(1) - 排序是原地进行的，只使用了常数级别的额外空间

Discussions